//
// Created by 麻再挺 on 2021/1/21.
//

#include "linked_list_impl.h"

/**
 * 创建线性链表
 * @param list 链表
 * @return
 */
Status Linked_List_Create(LinkedList *list) {
    // 创建带头结点的链表
    list = (LinkedList *) malloc(sizeof(LinkedList));
    // 判断是否溢出
    if (!list) return OVERFLOW;
    // 头结点指针值为 NULL
    list->next = NULL;
    // 数据值为0
    list->data = 0;

    return OK;
}

/**
 * 向末尾结点添加数据
 * @param list 链表
 * @param elem 数据
 * @return
 */
Status Linked_List_Push(LinkedList *list, ElemType elem) {
    // 赋值临时变量
    LinkedList *p = list;
    // 获取最后一个结点
    while (p && p->next) p = p->next;
    // 申请结点内存
    LinkedList *s = (LinkedList *) malloc(sizeof(LinkedList));
    // 判断是否溢出
    if (!s) return OVERFLOW;
    // 赋值
    s->data = elem;
    // 设置结点指针值为 NULL
    s->next = NULL;
    // 设置最后一个结点指向新创建的结点
    p->next = s;
    return OK;
}

/**
 * 向指定位置插入数据
 * @param list 链表
 * @param i 索引
 * @param elem 数据
 * @return
 */
Status Linked_List_Insert(LinkedList *list, int i, ElemType elem) {
    // 赋值临时变量
    LinkedList *p = list;
    // 设置临时变量索引
    int j = 0;
    // 遍历获取指定结点, 当前结点不为空并且临时索引值必须小于当前插入索引
    while (p && j < i) {
        // 获取下一个结点
        p = p->next;
        // 向右移位, 索引自加
        j++;
    }
    // 结点是否为空, 或者当前索引是否大于待插入位置
    if (!p || j > i) return ERROR;
    // 符合条件
    // 申请结点内存
    LinkedList *s = (LinkedList *) malloc(sizeof(LinkedList));
    // 判断是否溢出
    if (!s) return OVERFLOW;
    // 赋值
    s->data = elem;
    // 赋值指针值
    s->next = p->next;
    // 设置当前结点的下一个结点为新创建的结点
    p->next = s;
    return OK;
}

/**
 * 移除末尾结点数据
 * @param list 链表
 * @return
 */
Status Linked_List_Pop(LinkedList *list) {
    // 赋值临时变量
    LinkedList *p = list;
    // 获取尾结点的前一结点
    while (p && p->next && p->next->next) p = p->next;
    // 清空下一个结点数据
    p->next->data = 0;
    // 设置下一结点为空
    p->next = NULL;

    return OK;
}

/**
 * 删除指定位置元素
 * @param list 链表
 * @param i 索引
 * @return
 */
Status Linked_List_Delete(LinkedList *list, int i) {
    // 赋值临时变量
    LinkedList *p = list;
    // 设置临时变量索引
    int j = 0;
    // 遍历获取指定结点, 当前结点不为空并且临时索引值必须小于当前删除索引
    while (p && j < i) {
        // 获取下一个结点
        p = p->next;
        // 向右移位, 索引自加
        j++;
    }
    // 结点为空, 或者当前索引大于待删除位置
    if (!p->next || j > i) return ERROR;
    // 符合条件
    // 清空数据
    p->next->data = 0;
    // 设置结点指向下一位
    p->next = p->next->next;

    return OK;
}

/**
 * 根据索引获取链表数据
 * @param list 链表
 * @param i 索引
 * @param node 数据
 * @return
 */
Status Linked_List_Get_Elem(LinkedList *list, int i, LinkedList *node) {
    // 赋值临时变量
    LinkedList *p = list;
    // 设置临时变量索引
    int j = 0;
    // 遍历获取指定结点, 当前结点不为空并且临时索引值必须小于当前待获取索引
    while (p && j < i) {
        // 获取下一个结点
        p = p->next;
        // 索引自加
        j++;
    }
    // 结点为空, 或者当前索引大于待删除位置
    if (!p->next || j > i) return ERROR;
    // 赋值
    *node = *p->next;
    return OK;
}

/**
 * 合并两个线性链表, 合并后将值赋值到第一个链表中
 * @param list1 待合并线性链表, 合并后链表关系保存在 list1 中
 * @param list2 待合并线性链表, 合并后释放链表 list2
 * @return
 */
Status Linked_List_Merge(LinkedList *list1, LinkedList *list2) {
    // 创建临时链表
    LinkedList *pa = list1->next, *pb = list2->next, *pc = list1;
    // 遍历
    while (pa && pb) {
        if (pa->data <= pb->data) {
            // 赋值数据
            pc->next = pa;
            // 将 pc 移动到下一个
            pc = pa;
            // 获取下一个
            pa = pa->next;
        } else {
            // 赋值数据
            pc->next = pb;
            // 将 pc 移动到下一个
            pc = pb;
            // 获取下一个
            pb = pb->next;
        }
    }
    // 拼接后续内容
    pc->next = pa ? pa : pb;
    return OK;
}

/**
 * 打印链表数据
 * @param list 链表
 */
void Linked_List_Print(LinkedList *list) {
    // 赋值临时变量
    LinkedList *p = list->next;
    // 遍历打印
    while (p != NULL) {
        printf("%d\t", p->data);
        // 获取下一个结点
        p = p->next;
    }
    printf("\n");
}